/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    queue<TreeNode*>Q;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==NULL) return {};
        vector<vector<int>> ans = {};
        bfs_in_line(root, ans);
        return ans;
    }

    void bfs(TreeNode* root, vector<int>& ans){
        Q.push(root);// root数据入队列
        while(!Q.empty()){
            //下面为简单bfs的主要出入队列过程
            TreeNode* node = Q.front();
            ans.push_back(node->val);
            if(node->left!=NULL)
                Q.push(node->left);
            if(node->right!=NULL)
                Q.push(node->right);
            Q.pop();
        }
        return;
    }

    void bfs_in_line(TreeNode* root, vector<vector<int>>& ans){
        vector<TreeNode*> Queue = vector<TreeNode*>(2005);
        int head = 0, tail = 0;
        Queue[tail++] = root;
        vector<int> *line = new vector<int>();
        while(head<tail){
            //下面为简单bfs的主要出入队列过程
            int length = tail;   //这一步主要用于防止队列tail自增影响结果
            for(int i=head;i<length;i++){
                TreeNode* node = Queue[i];
                line->push_back(node->val);
                if(node->left!=NULL)
                    Queue[tail++] = node->left;
                if(node->right!=NULL)
                    Queue[tail++] = node->right;
                head++;
            }
            ans.push_back(*line);
            line = new vector<int>();
        }
        return;
    }
    
    //第一行正序，第二行逆序
    void bfs_in_line_RE(TreeNode* root, vector<vector<int>>& ans){
        vector<TreeNode*> Queue = vector<TreeNode*>(2005);
        int head = 0, tail = 0;
        Queue[tail++] = root;
        int flag = 0;
        vector<int> *line = new vector<int>();
        while(head<tail){
            //下面为简单bfs的主要出入队列过程
            int length = tail;
            for(int i=head;i<length;i++){
                TreeNode* node = Queue[i];
                line->push_back(node->val);
                if(node->left!=NULL)
                    Queue[tail++] = node->left;
                if(node->right!=NULL)
                    Queue[tail++] = node->right;
                head++;
            }
            if((flag++)%2==0)
                reverse(line->begin(), line->end());
            ans.push_back(*line);
            line = new vector<int>();
        }
        return;
    }

};
int main(){
    TreeNode* head = new TreeNode(3);
    head->left = new TreeNode(9);
    head->right = new TreeNode(20);
    Solution().levelOrder(head);
    return 0;
}